Subdivision surfaces are emerging as a powerful representation for shape design. Their simplicity and potential to overcome difficulties associated with traditional spline-based modeling has made them a popular choice for several applications, including industrial modeling, movie production, and games.
Subdivision defines a smooth surface recursively, as the limit of a sequence of meshes. A finer mesh is obtained from a coarse mesh by applying a set of fixed refinement rules, for example the Catmull-Clark rules (see Catmull, E. and Clark, J., Recusively Generated B-Spline Surfaces on Arbitrary Topological Meshes, CAD 10 (6), pp. 350-355, 1978). The initial, coarsest mesh is also known as the base mesh. FIG. 2 shows a prior art example of a base mesh and a sequence of refinements that lead to a smooth surface. A subdivision surface (FIG. 2E) is generated from an initial control polyhedron (FIG. 2A) by repeated subdivision (FIGS. 2B-2D). Control meshes obtained at several intermediate subdivision steps are shown in the middle (FIGS. 2B-2D). In this example, the Catmull-Clark subdivision scheme was applied.
The initial coarsest mesh serves as a base domain over which the resulting surface is naturally parameterized. See FIG. 3. Intuitively, the correspondence between control points on a given subdivision level and points in the base domain can be illustrated using two copies of the base mesh and applying in parallel midpoint subdivision on one copy (FIG. 3A) and Catmull-Clark subdivision on the other (FIG. 3B), as illustrated in FIG. 3. This ability to cast subdivision surfaces as parametric surfaces over a domain is crucial for many operations on this type of representation.
Some formal background on the definition and properties of natural parameterizations is now provided. A review of existing methods for exact evaluation at arbitrary parameter values is also included.
Throughout this disclosure, we use the term control point (or simply point) to refer to points computed by subdivision. We also use the term vertex to designate vertices of the polyhedron that serves as a base domain, as well as vertices added to it by midpoint subdivision. We also make use of the concepts of valence and extraordinary vertex/point. The valence of a vertex is an integer number equal to the number of faces incident to that vertex. A vertex is termed boundary vertex if it lies on the boundary of an open mesh. A vertex which is not a boundary vertex is called an interior vertex. For Catmull-Clark meshes, an interior vertex of the base mesh which has a valence different than four or a boundary vertex with valence different than two is deemed extraordinary (see vertex marked with circle 210 in FIG. 2A). The concepts of 1-ring and 2-ring around a vertex allow us to refer to the mesh neighborhood around that vertex. The 1-ring around a vertex is defined as the set of vertices belonging to faces adjacent to that vertex. The 2-ring around a vertex is defined as the set formed by the union of its 1-ring and the 1-rings of the vertices in the 1-ring different from the vertex itself. Parallel definitions can be obtained from the definitions above by replacing the word “vertex” with the word “point” to define the concepts of boundary point, interior point, extraordinary point, and 1-ring and 2-ring around a point.
More formally, let D denote the subset of R3 corresponding to the base domain. Repeated subdivision generates a sequence of piecewise linear maps defined over the common domain, D. When this sequence converges uniformly (as it is the case for the Catmull-Clark scheme), the limit map ƒ: D→R3 defines the limit surface of subdivision. For the Catmull-Clark scheme, the limit surface around an extraordinary point is completely defined by the set of points in the 2-ring around the extraordinary point. This set is called a control set. Let ƒ[p] denote the limit surface generated by subdivision from the control set p. For converging subdivision schemes, the limit function of subdivision can be decomposed into a sum of basis functions:
                                          f            ⁡                          [              p              ]                                ⁢                      (                          u              ,              v                        )                          =                              ∑            i                    ⁢                                    a              i                        ⁢                                          f                i                            ⁡                              (                                  u                  ,                  v                                )                                                                        (        1        )            
These so-called eigenbasis functions are the limit functions generated by the eigenvectors of the subdivision matrix S: ƒi:=ƒ[xi], where xi is the eigenvector of the subdivision matrix S corresponding to the eigenvalue λi: Sxi=λixi. It has been shown in Zorin, D. Subdivision and Multiresolution Surface Representations. Pd.D. Thesis, Caltech, 1997 that the eigenbasis functions satisfy the following scaling relation:
                                          f            i                    ⁡                      (                                          u                2                            ,                              v                2                                      )                          =                              λ            i                    ⁢                                    f              i                        ⁡                          (                              u                ,                v                            )                                                          (        2        )            
It is possible to directly evaluate subdivision surfaces and their derivatives up to any order at arbitrary parameter values without the need for explicit subdivision, as proposed in Stam, J., Exact Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter Values, Proceedings of Siggraph 98, pp. 395-404, 1998 and in Zorin, D. and Kristjansson, D., Evaluation of Piecewise Smooth Subdivision Surfaces, Visual Computer, 2002.
The evaluation algorithm described in Zorin, D. and Kristjansson, D., Evaluation of Piecewise Smooth Subdivision Surfaces, Visual Computer, 2002 is now reviewed in the context of the Catmull-Clark subdivision scheme.
The evaluation problem can be stated as follows: “Given a quadrilateral face j of the base mesh parameterized over the unit square [0,1]×[0,1] and parametric coordinates (u, v) within this face, find the value of the subdivision surface ƒ(u, v, j)∈R3 at this parameter value.”
If the given quadrilateral face contains no extraordinary vertices, the surface can be evaluated as a bi-cubic spline patch defined by the control vertices of the face after an additional subdivision step. If the face contains extraordinary vertices, we can assume without restricting the generality of the problem, that it has a single extraordinary vertex (otherwise the problem can be reduced to this case after one subdivision step).
Let y=(u, v, j) be a point in the domain of the surface different from an extraordinary vertex. An important observation is that there exists a sufficiently fine subdivision level m such that y is located ina quadrilateral  on level m and the control mesh of  does not contain any extraordinary vertices. This means that the surface over  is polynomial and can be evaluated explicitly (including at pointy) using bi-cubic spline evaluation. Obviously, for points closer to the extraordinary vertex, the level m is higher than for points farther away. This interpretation leads to a conceptual decomposition of the neighborhood around an extraordinary vertex into concentric layers. These layers correspond to the number of subdivision steps required to isolate the location being evaluated from the extraordinary vertex. Formally, if S denotes the subdivision matrix, the control meshes of quadrilaterals on level m can be computed from the initial control mesh by a multiplication with the m-th power of the subdivision matrix: Sm. These observations lead to a direct evaluation algorithm as outlined in the pseudo-code of Algorithm 1 and as illustrated in the flowchart of FIG. 5.
Problems with the Prior Art
By definition, a surface ƒ: D→R3 is C1-continuous if for any point x∈D there is a neighborhood of x, Ux⊂D and a regular parameterization of ƒ(Ux) over the unit disk in the plane. Intuitively, this means that a surface is smooth around a given point if it behaves like a plane in its immediate vicinity.
According to this definition, the proof that the limit surface generated by a subdivision scheme is C1-continuous around an extraordinary point amounts to showing that a regular parameterization as required in the definition exists at that point. It has been shown that, in the case of Catmull-Clark surfaces, such a parameterization exists and hence, they are C1-continuous (see below also). However, it turns out that at the extraordinary points, the natural parameterization discussed above, do not satisfy the regularity requirement for valences greater than 4. To prove that this is the case, consider the neighborhood around an extraordinary vertex and expressions (1) and (2). For simplicity, we assume that the extraordinary vertex is situated at the origin (i.e., ai=0).
If we derivate expression (1) with respect to u, we obtain:
            ∂              ∂        u              ⁢          f      ⁡              [        p        ]              ⁢          (              u        ,        v            )        =            ∑      i        ⁢                  a        i            ⁢              ∂                  ∂          u                    ⁢                        f          i                ⁡                  (                      u            ,            v                    )                    
The expression of the derivative with respect to v is similar and omitted for brevity. From (2), we have:
            ∂              ∂        u              ⁢                  f        i            ⁡              (                              u            2                    ,                      v            2                          )              =            (              2        ⁢                  λ          i                    )        ⁢          ∂              ∂        u              ⁢                  f        i            ⁡              (                  u          ,          v                )            and by induction,
                                          ∂                          ∂              u                                ⁢                                    f              i                        ⁡                          (                                                u                                      2                    m                                                  ,                                  v                                      2                    m                                                              )                                      =                                            (                              2                ⁢                                  λ                  i                                            )                        m                    ⁢                      ∂                          ∂              u                                ⁢                                    f              i                        ⁡                          (                              u                ,                v                            )                                                          (        3        )            
From (3), it follows that for m→∞ the value
      ∂          ∂      u        ⁢            f      i        ⁡          (              0        ,        0            )      is unbounded if (2λi)>1. For the Catmull-Clark scheme, the subdominant eigenvalue is larger than ½ for valences greater than 4, which proves our claim that derivatives computed based on the natural parameterization diverge around extraordinary points corresponding to extraordinary vertices of valence greater than 4. Using the same argument, if (2λi)<1 the value of
      ∂          ∂      u        ⁢            f      i        ⁡          (              0        ,        0            )      is zero for m→∞. This is the case for extraordinary points corresponding to extraordinary vertices of valence 3. FIG. 4 illustrates the behavior of the iso-parameter lines around extraordinary vertices of valence 3 (FIG. 4A), 5 (FIG. 4B), and 13 (FIG. 4C), respectively. Intuitively, the behavior of the derivatives can be observed by examining the spacing between iso-parameter lines. For valences greater than 4, the spacing between consecutive lines increases as they approach the extraordinary point as the derivatives diverge. For valence 3 the spacing between iso-parameter lines decreases as the derivatives converge to zero.
All references cited above are herein incorporated by reference in their entirety.
Aspects of the Invention
An aspect of the invention is an improved system and method for general three-dimensional surface modeling.
An aspect of the invention is an improved system and method for re-parameterizing three-dimensional models represented as Catmull-Clark subdivision surfaces.
An aspect of the invention is an improved system and method for surface evaluation in solid modeling.